package toOffer;

/**
 * @author YuanAo
 * @date 2024/12/16 10:09
 * @description 合并区间
 */

import java.util.*;

/**
 * 输入一个区间的集合，请将重叠的区间合并。每个区间用两个
 * 数字比较，分别表示区间的起始位置和结束位置。例如，输入区间[[1, 3], [4,
 * 5], [8, 10], [2, 6], [9, 12], [15, 18]]，合并重叠的区间之后得到[[1, 6], [8, 12],
 * [15, 18]]。
 */
public class toOffer12_1_74 {
    public static void main(String[] args) {
        int[] ints1 = new int[]{1, 3};
        int[] ints2 = new int[]{2, 6};
        int[] ints3 = new int[]{4, 5};
        int[] ints4 = new int[]{8, 10};
        int[] ints5 = new int[]{9, 12};
        int[] ints6 = new int[]{15, 18};
        int[][] intervals = new int[][]{ints1, ints2, ints3, ints4, ints5, ints6};
        int[][] elements = merge(intervals);
        for (int[] element : elements) {
            System.out.println(element[0] + "-" + element[1]);
        }
    }

    public static int[][] merge(int[][] intervals) {
        // 按照每组第一个数字升序排序
        Arrays.sort(intervals, ((o1, o2) -> o1[0]-o2[0]));
        List<int[]> ints = new ArrayList<>();
        int i = 0;
        while (i < intervals.length){
            int[] temp = new int[]{intervals[i][0], intervals[i][1]};
            int j = i + 1;
            while (j < intervals.length && intervals[j][0] < temp[1]){
                temp[1] = Math.max(intervals[j][1], temp[1]);
                j++;
            }
            ints.add(temp);
            i = j;
        }

        int[][] set = new int[ints.size()][];
        return ints.toArray(set);
    }

}
